package com.likou;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class q230 {

//    public int kthSmallest(TreeNode root, int k) {
//        Deque<TreeNode> deque = new LinkedList<>();
//        TreeNode p = root;
//        List<Integer> list = new ArrayList<>();
//
//        while (p != null || !deque.isEmpty()) {
//            while (p != null) {
//                deque.push(p);
//                p = p.left;
//            }
//
//            TreeNode pop = deque.pop();
//            list.add(pop.val);
//            p = pop.right;
//        }
//
//        return list.get(k - 1);
//
//    }

//    public int kthSmallest(TreeNode root, int k) {
//        TreeNode p = root;
//        List<Integer> list = new ArrayList<>();
//        DFS(root, list);
//        return list.get(k - 1);
//
//    }
//
//    private void DFS(TreeNode root, List<Integer> list) {
//        if (root == null) {
//            return;
//        }
//
//        DFS(root.left, list);
//        list.add(root.val);
//        DFS(root.right, list);
//    }


    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode p = root;
        int mark = 0;
        int ans = 0;

        while (p != null || !deque.isEmpty()) {
            while (p != null) {
                deque.push(p);
                p = p.left;
            }

            TreeNode pop = deque.pop();
            mark++;
            if (mark == k) {
                ans = pop.val;
                break;
            }
            p = pop.right;
        }

        return ans;

    }
}
